package _go

/*20. 有效的括号
难度
简单

2708

收藏

分享
切换为英文
接收动态
反馈
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。


示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true


提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
通过次数803,425提交次数1,804,871*/

func isValid(s string) bool {
	n := len(s)
	if n == 0 {
		return true
	}
	//奇数个肯定不合法
	if n%2 == 1 {
		return false
	}
	stark := []byte{} //更省空间
	//先定义一个map 能方便判断
	hashMap := map[byte]byte{'}': '{', ')': '(', ']': '['}
	//O(n)的时间复杂度 需要遍历n次
	for i := 0; i < n; i++ {
		//如果读取到右边的值  就需要判断一下是不是合法了
		if hashMap[s[i]] > 0 {
			//如果栈为空 或者 栈顶的值不等于相应的左边 直接返回
			//这个地方有个小语法糖 切片可以直接读取最后一个值 直接输出值类型 而不是切片类型
			if len(stark) == 0 || stark[len(stark)-1] != hashMap[s[i]] {
				return false
			}
			//如果匹配就直接出栈
			stark = stark[:len(stark)-1]
		} else { //左边的值直接入栈就好
			stark = append(stark, s[i])
		}
	}
	return len(stark) == 0
}
